package com.lw.leetcode.hash.b;

import java.util.HashMap;
import java.util.Map;

/**
 * hash
 * 873. 最长的斐波那契子序列的长度
 * 剑指 Offer II 093. 最长斐波那契数列
 *
 * @Author liw
 * @Date 2021/8/2 22:12
 * @Version 1.0
 */
public class LenLongestFibSubseq {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            index.put(arr[i], i);
        }
        Map<Integer, Integer> longest = new HashMap<>();
        int ans = 0;

        for (int k = 0; k < n; ++k)
            for (int j = 0; j < k; ++j) {
                int i = index.getOrDefault(arr[k] - arr[j], -1);
                if (i >= 0 && i < j) {
                    // Encoding tuple (i, j) as integer (i * N + j)
                    int cand = longest.getOrDefault(i * n + j, 2) + 1;
                    longest.put(j * n + k, cand);
                    ans = Math.max(ans, cand);
                }
            }

        return ans >= 3 ? ans : 0;
    }

}
